package two.chapter_3.c3_1;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_1.c1_3.CollectionEmptyException;
import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;

public class BST<Key extends Comparable<Key>, Value> implements SeqST<Key, Value> {


    private Node root;//根结点

    /**
     * 一直沿着左子树查找
     *
     * @return
     */
    @Override
    public Key min() {
        checkEmpty();
        return min(root).key;
    }

    private void checkEmpty() {
        if (isEmpty()) {
            throw new CollectionEmptyException();
        }
    }

    private Node min(Node node) {

        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    @Override
    public Key max() {
        checkEmpty();
        return max(root);
    }

    private Key max(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node.key;
    }

    /**
     * 返回小于等于指定key的最大key
     *
     * @param key
     * @return
     */
    @Override
    public Key floor(Key key) {
        Node node = floor(root, key);
        if (node == null) {
            return null;
        }
        return node.key;
    }

    /**
     * 和根节点比较，若小于根节点，则出现在左子树中
     * 若大于根节点时在右子树中存在小于等于key的结点，那么就出现在右子树中，否则就是根节点
     *
     * @param node
     * @param key
     * @return
     */
    private Node floor(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp == 0) {
            return node;
        } else if (cmp > 0) {
            return floor(node.left, key);
        }

        Node t = floor(node.right, key);
        if (t != null) {
            return t;
        } else {
            return node;
        }

    }

    /**
     * 1，根结点key和指定key比较
     * =时，直接返回根结点
     * <时，那么必须出现在右子树中
     * >时，存在相等的key时，返回相等的node，不存在则ceiling值就是根结点
     *
     * @param key
     * @return
     */
    @Override
    public Key ceiling(Key key) {

        Node node = ceiling(root, key);
        if (node == null) {
            return null;
        }


        return node.key;
    }

    private Node ceiling(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp == 0) {
            return node;
        } else if (cmp < 0) {
            return ceiling(node.right, key);
        }
        Node t = ceiling(node.left, key);
        if (t == null) {
            return node;
        }
        return t;

    }

    /**
     * @param key
     * @return
     */
    @Override
    public int rank(Key key) {


        return rank(root, key);
    }

    private int rank(Node node, Key key) {
        if (node == null) {
            return 0;
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            return rank(node.left, key);
        } else if (cmp > 0) {
            return 1 + size(node.left) + rank(node.right, key);
        } else {
            return size(node.left);
        }
    }

    /**
     * 返回排名为k的键
     *
     * @param k
     * @return
     */
    @Override
    public Key select(int k) {
        Node node = select(root, k);
        if (node == null) return null;

        return node.key;


    }

    private Node select(Node node, int k) {
        if (node == null) return null;
        int size = size(node.left);
        if (size > k) {
            return select(node.left, k);
        } else if (size < k) {
            return select(node.right, k - size - 1);
        } else {
            return node;
        }
    }

    /**
     * 删除最小键
     * 步骤：
     * 深入左子树，一直到左子树为null，将该结点的父结点指针指向右子树
     */
    @Override
    public void deleteMin() {
        checkEmpty();
        root = deleteMin(root);

    }

    private Node deleteMin(Node node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    @Override
    public void deleteMax() {
        root = deleteMax(root);
    }

    private Node deleteMax(Node node) {
        if (node.right == null) {
            return node.left;
        }
        node.right = deleteMax(node.right);
        node.size = size(node.right) + size(node.left) + 1;
        return node;
    }

    @Override
    public int size(Key lo, Key hi) {
        return 0;
    }

    /**
     * 使用中序遍历 遍历整个树
     *
     * @param lo
     * @param hi
     * @return
     */
    @Override
    public Iterable<Key> keys(Key lo, Key hi) {
        Queue<Key> queue = new LinkedQueue<>();
        keys(root, queue, lo, hi);
        return queue;
    }

    private void keys(Node node, Queue<Key> queue, Key lo, Key hi) {
        if (node == null) {
            return;
        }
        int cmpLo = node.key.compareTo(lo);
        int cmpHi = node.key.compareTo(hi);
        keys(node.left, queue, lo, hi);
        if (cmpLo >= 0 && cmpHi <= 0) {
            queue.enqueue(node.key);
        }
        keys(node.right, queue, lo, hi);

    }

    @Override
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    private Node put(Node node, Key key, Value value) {
        if (node == null) {
            return new Node(key, value);
        }
        int cmp = node.key.compareTo(key);
        if (cmp == 0) {
            node.value = value;//更新
            //return node;
        } else if (cmp > 0) {
            node.left = put(node.left, key, value);
        } else {
            node.right = put(node.right, key, value);
        }
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    @Override
    public Value get(Key key) {
        return get(root, key);

    }

    private Value get(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp == 0) {
            return node.value;
        } else if (cmp > 0) {
            return get(node.left, key);
        } else {
            return get(node.right, key);
        }
    }

    /**
     * 删除指定的key
     * 步骤：
     * 0,关键：查找与指定key相等的结点
     * 1，即将删除的结点链接保存为t
     * 2，x指向它的后继结点min(t.right)
     * 3,将x的右链接指向deleteMin(t.right)
     * 4,将x的左链接设为t.left
     *
     * @param key
     */
    @Override
    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = delete(node.right, key);
        } else if (cmp < 0) {
            node.left = delete(node.left, key);
        } else {

            if (node.right == null) {
                return node.left;
            }
            if (node.left == null) {
                return node.right;
            }
            Node t = node;
            node = min(t.right);
            node.right = deleteMin(t.right);
            node.left = t.left;
        }
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }


    private Node find(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp == 0) {
            return node;
        } else if (cmp > 0) {
            return find(node.left, key);
        } else {
            return find(node.right, key);
        }
    }

    @Override
    public boolean contains(Key key) {
        return get(key)!=null;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return root.size;
    }

    private int size(Node node) {
        if (node == null)
            return 0;
        return node.size;
    }

    @Override
    public Iterable<Key> keys() {
        return keys(min(), max());
    }


    private class Node {

        Key key;
        Value value;
        int size;//个数
        Node left;
        Node right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            this.size = 1;
        }
    }
}
